/*
		高精度乘法(模拟乘法的过程)
*/

/*---------------------------------------------------------------------------------------------------------*/
vector<int> analog_multiplication(const vector<int>& x, const vector<int>& y)
{
	vector<vector<int>> matrix;						//存放部分积
	for (int i = y.size() - 1; i >= 0; i--){
		int carry = 0;								//进位(开始时为0)
		vector<int> middle_item;					//中间项
		for (int j = x.size() - 1; j >= 0; j--){
			int tmp = x[j] * y[i] + carry;
			int bit = tmp % 10;
			middle_item.push_back(bit);				//这里的中间项是反着的
			carry = tmp / 10;
		}
		if (carry != 0)								//最后进位可能不为0, 要加上!!!
			middle_item.push_back(carry);
		matrix.push_back(middle_item);
	}
	int row = matrix.size();
	int col = matrix[row - 1].size() + row - 1;		//建立一个二维数组, 方便错位相加
	vector<vector<int>> partial_product;			//前后补上0的部分积, 方便相加
	for (int i = 0; i < row; i++){
		vector<int> tmp;
		for (int j = 0; j < i; j++)					//第0行补上0个0, 第1行补上1个0,以此类推
			tmp.push_back(0);
		for (int j = 0; j < matrix[i].size(); j++)
			tmp.push_back(matrix[i][j]);
		while(tmp.size() < col)
			tmp.push_back(0);						//若不够列数还要补0
		partial_product.push_back(tmp);
	}

	vector<int> ret;								//部分积相加的结果
	int carry = 0;									//进位
	for (int i = 0; i < col; i++){
		int sum = 0;
		for (int j = 0; j < row; j++)
			sum += partial_product[j][i];			//每列求和
		sum += carry;
		int bit = sum % 10;
		ret.push_back(bit);
		carry = sum / 10;
	}
	if (carry != 0)									//进位不为0要补上!!!
		ret.push_back(carry);
	while (ret[ret.size() - 1] == 0)				//将后面多余的0去除
		ret.pop_back();
	reverse(ret.begin(), ret.end());				//在计算时,我们表示的数是反着的, 这里需要逆置,该函数需要头文件#include<algorithm>
	return ret;
}
/*---------------------------------------------------------------------------------------------------------*/